import java.util.HashMap;
import java.util.Map;

/**
 * @author SongJun
 * @description 凑零钱(动态规划)
 * @date 2021/9/8 14:21
 */
public class Coins {
    public static void main(String[] args) {
        int[] coins = {184,419,408};
        int amount = 827;
        Map<String, Integer> bestMap = new HashMap<>();
        int a = compute(coins, amount, bestMap);
        System.out.println(a);
    }

    public static int compute(int[] coins, int amount, Map<String, Integer> bestMap){
        //结束条件
        if(amount < 0){
            return -1;
        } else if(amount == 0){
            return 0;
        }
        //查备忘录
        if(bestMap.containsKey(String.valueOf(amount))){
            return bestMap.get(String.valueOf(amount));
        }
        int min = Integer.MAX_VALUE;
        //做选择
        for(int coin : coins){
            //计算上一步的结果
            int sub = compute(coins, amount - coin, bestMap);
            //选出最优的结果
            if(sub >= 0 && sub < min){
                min = sub + 1;
            }
        }
        //存备忘录
        if(min == Integer.MAX_VALUE){
            bestMap.put(String.valueOf(amount), -1);
            return -1;
        } else {
            bestMap.put(String.valueOf(amount), min);
            return min;
        }
    }
}
